package q0126;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：
 * <p>
 * 每次转换只能改变一个字母。
 * 转换过程中的中间单词必须是字典中的单词。
 * 说明:
 * <p>
 * 如果不存在这样的转换序列，返回一个空列表。
 * 所有单词具有相同的长度。
 * 所有单词只由小写字母组成。
 * 字典中不存在重复的单词。
 * 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
 * 示例 1:
 * <p>
 * 输入:
 * beginWord = "hit",
 * endWord = "cog",
 * wordList = ["hot","dot","dog","lot","log","cog"]
 * <p>
 * 输出:
 * [
 * ["hit","hot","dot","dog","cog"],
 *   ["hit","hot","lot","log","cog"]
 * ]
 * 示例 2:
 * <p>
 * 输入:
 * beginWord = "hit"
 * endWord = "cog"
 * wordList = ["hot","dot","dog","lot","log"]
 * <p>
 * 输出: []
 * <p>
 * 解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/word-ladder-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author fangjiaxiaobai@gmail.com
 * @version 1.0.0
 * @date 2020-06-07
 */
public class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {

        // 首先遍历一遍所有数据找到是否存在 endWord,和最后一个beginWord的位置
        int startIndex = -1;
        int endIndex = wordList.size();
        for (int i = 0; i < wordList.size(); i++) {
            String word = wordList.get(i);
            if (word.equals(beginWord)) {
                startIndex = i;
            }
            if (word.equals(endWord)) {
                endIndex = i;
            }
        }
        if (endIndex == wordList.size()) {
            return null;
        }

        // 开始布局: 二维数组
        int[][] grid = new int[endIndex + 1][];
        grid[0][0] = 0;
        grid[0][1] = 0;

        int oneWordLength = wordList.get(0).length();
        int minValue = oneWordLength;
        for (int i = 0; i < wordList.size(); i++) {
            int minBetween = oneWordLength;
            for (int j = i + 1; j < wordList.size() + 1; j++) {
                String startWord = wordList.get(i);
                String endingWord = wordList.get(j);
                int between = grid[i][0] + checkWordBetween(startWord, endingWord);
                grid[i][j] = between;
                if (minBetween > between) {
                    minBetween = between;
                }
                // 记录到达最后字符串的最小值
                if (j == wordList.size() - 1 && grid[i][j] < minValue) {
                    minValue = grid[i][j];
                }
            }
            grid[1 + i][0] = minBetween;
        }

        // 遍历查找对应的路线
        List<List<String>> lists = new ArrayList<>();

        for (int i = grid[0].length; i > 0 && grid[oneWordLength][i] == minValue; i--) {
            int routeId = minValue;
            List<String> routes = new ArrayList<>();
            /// 广度优先遍历
            for (int j = i-1; j>0;j-- ) {
                for(int k=j-1;k>0;k--){
                    // BFS
                }
            }
        }


        return lists;
    }

    private int checkWordBetween(String startWord, String endingWord) {
        int between = 0;
        for (int i = 0; i < startWord.length(); i++) {
            if (startWord.charAt(i) != endingWord.charAt(i)) {
                between++;
            }
        }
        return between;
    }

    public static void main(String[] args) {

    }


}
